Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Leaf Processing Pattern (medium)
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Delete Leaves With a Given Value

Problem Statement

Given a root node of a binary tree and an integer target, delete all leaf nodes that have a value equal to target.

After removing such leaf nodes, if any of their parent nodes become leaf nodes with a value equal to target, they should also be removed. This process should continue until no more nodes can be deleted.

Examples

Example 1

  • Input: root = [1, 5, 3, 5, null, 5, 4], Target: 5
Image
  • Expected Output: [1,null,3,null,4]
  • Explanation: The left child of 5 (left of root) is 3 and 5. When we remove both leaf having value 5, the left node of the root also becomes a leaf having a value equal to 5. So, we also remove it.

Example 2

  • Input: root = [3, 3, 3, 3, 3, null, 4], Target: 3
Image
  • Expected Output: [3,null,3,null,4]
  • Explanation: Remove all 3 except the root and right child of the root node.

Example 3

  • Input: root = [4, 5, 6, 5, null, 7, 8], Target: 5
Image
  • Expected Output: [4,null,6,7,8]
  • Explanation: The leaf nodes with value 5 are removed first. The tree becomes [4, 5, 6, null, null, 7, 8]. Now, again remove the leaf node with the value 5 and the tree becomes [4, null, 6, 7, 8]`.

Constraints:

  • The number of nodes in the tree is in the range [1, 3000].
  • 1 <= Node.val, target <= 1000

Solution

To solve this problem, we use a recursive depth-first search (DFS) approach. We start from the root of the tree and recursively process the left and right subtrees to remove all leaf nodes with the given target value. During each recursive call, if a node becomes a leaf and its value matches the target, we remove it by returning null. This process continues until no target leaf nodes remain in the tree, ensuring that all eligible nodes are removed even if their parent nodes later become leaf nodes with the target value.

Step-by-Step Algorithm

  1. Check if the Current Node is Null:

    • If root is null, return null. This handles cases where the tree or subtree is empty.
  2. Recursively Process the Left Subtree:

    • Call removeLeafNodes(root.left, target) to remove target leaf nodes from the left subtree.
    • Update root.left with the returned value.
  3. Recursively Process the Right Subtree:

    • Call removeLeafNodes(root.right, target) to remove target leaf nodes from the right subtree.
    • Update root.right with the returned value.
  4. Check if the Current Node is a Target Leaf:

    • If root.left and root.right are both null and root.val equals the target, it means the current node is a target leaf node.
    • Return null to remove the current node if it matches the target value and is a leaf.
  5. Return the Updated Node:

    • If the current node is not a target leaf, return root to retain the node in the updated tree.

Step-by-Step Algorithm Walkthrough

Given the input:

  • Tree: [1, 5, 3, 5, null, 5, 4]
  • Target: 5
  1. Start at the Root Node 1:

    • root is 1, call removeLeafNodes on root.left (node 5).
  2. Process Left Child 5 of Root 1:

    • root is 5, call removeLeafNodes on root.left (node 5).
  3. Process Left Child 5 of Node 5:

    • It is leaf node and value is equal to target(5). So, return null.
  4. Return to Node 5 (Left Child of Root 1):

    • root.left is null.
    • Call removeLeafNodes on root.right (null) — returns null.
    • root is a target leaf (val = 5), return null.
  5. Return to Root Node 1:

    • root.left is updated to null.
    • Call removeLeafNodes on root.right (node 3).
  6. Process Right Child 3 of Root 1:

    • root is 3, call removeLeafNodes on root.left (node 5).
  7. Process Left Child 5 of Node 3:

    • It is leaf node and value is equal to target(5). So, return null.
  8. Return to Node 3:

    • root.left is null.
    • Call removeLeafNodes on root.right (node 4) — returns node 4.
  9. Complete Processing Node 3:

    • root.right is 4, not a target leaf, so return 3.
  10. Finish at Root Node 1:

    • root.left is null and root.right is 3. Return 1 as the final root.

Resulting tree after removal is: [1, null, 3, null, 4].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The algorithm uses a depth-first search (DFS) to traverse the binary tree. In the worst case, the DFS will visit every node in the tree once. Thus, the time complexity is , where n is the total number of nodes in the binary tree.

Space Complexity

The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the height of the binary tree. In the worst case, the height of the tree could be for a skewed tree (where every node has only one child), resulting in a space complexity of .

Delete Leaves With a Given Value (medium)
Deepest Leaves Sum (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Step-by-Step Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity